package org.example.leetcode.interview.dp;

public class LC0091 {
    public int numDecodings(String s) {
        if (s.length() == 0) return 0;
        if (s.charAt(0) == '0') return 0;

        int[] dp = new int[s.length() + 1];
        dp[0] = 1;
        for (int i = 0; i < s.length(); i++) {
            char curr = s.charAt(i);
            dp[i + 1] = curr == '0' ? 0 : dp[i];
            // 处理特殊情况, 组合是26 或者 1xx
            if (i > 0) {
                char prev = s.charAt(i - 1);
                if (prev == '1' || (prev == '2' && curr <= '6')) {
                    dp[i + 1] += dp[i - 1];
                }
            }
        }

        return dp[s.length()];
    }

}
